import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
* @description: 986. 区间列表的交集
* @author hewei
* @date 2022/10/4 14:22
* @version 1.0
*/

public class IntervalIntersection {

    public int[][] intervalIntersection1(int[][] firstList, int[][] secondList) {
        List<int[]> list = new ArrayList<>();
        list.addAll(Arrays.asList(firstList));
        list.addAll(Arrays.asList(secondList));
        list.sort((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            return a[1] - b[1];
        });
        if (list.size() == 0) return new int[0][0];
        int end = list.get(0)[1];
        List<int[]> res = new ArrayList<>();
        for (int i = 1; i < list.size(); i++) {
            int[] temp = list.get(i);
            if (temp[0] >= end) {
                if (temp[0] == end) res.add(new int[]{end, end});
                end = temp[1];
            } else if (temp[1] >= end) {
                res.add(new int[]{temp[0], end});
                end = temp[1];
            } else {
                res.add(new int[]{temp[0], temp[1]});
            }
        }
        int[][] ans = new int[res.size()][2];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }

    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int p1 = 0, p2 = 0;
        List<int[]> res = new ArrayList<>();
        while (p1 < firstList.length && p2 < secondList.length) {
            int end1 = firstList[p1][1];
            int end2 = secondList[p2][1];
            int start1 = firstList[p1][0];
            int start2 = secondList[p2][0];
            if (end1 > end2) {
                if (start1 <= end2) res.add(new int[]{Math.max(start2, start1), end2});
                ++p2;
            } else {
                if (start2 <= end1) res.add(new int[]{Math.max(start2, start1), end1});
                ++p1;
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}
